// 题目描述
// 讨论 (1.6K)
// 32. 最长有效括号
// 困难
// 2.3K
// 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//   示例 1：
// 输入：s = "(()"
// 输出：2
// 解释：最长有效括号子串是 "()"
// 示例 2：
// 输入：s = ")()())"
// 输出：4
// 解释：最长有效括号子串是 "()()"
// 示例 3：
// 输入：s = ""
// 输出：0
//   提示：
// 0 <= s.length <= 3 * 104
// s[i] 为 '(' 或 ')'
// 通过次数
// 387.5K
// 提交次数
// 1M
// 通过率
// 37.3%
// https://leetcode.cn/problems/longest-valid-parentheses/

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  let ans = 0
  const sk = []
  const dp = new Array(s.length + 1).fill(0)
  for (let i = 0; i < s.length; i++) {
    if (s.charAt(i) === '(') {
      sk.push(i)
      dp[i + 1] = 0
    } else {
      // 遇到右括号
      if (sk.length) {
        // 配对的左括号对应索引
        const leftIdx = sk.pop()
        const len = 1 + i - leftIdx + dp[leftIdx]
        dp[i + 1] = len
        ans = Math.max(ans, len)
      } else {
        // 没有配对的左括号
        dp[i + 1] = 0
      }
    }
  }

  return ans
}


console.log(
  longestValidParentheses('')
)
